//
// Created by dengspc on 2019/1/28.
//

#ifndef INC_010_ALGORITHM_AVL_H
#define INC_010_ALGORITHM_AVL_H

#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

template <typename Key,typename Value>
class AVLTree:public SearchTree<Key,Value>{
private:
    struct Node {
        Key key;
        Value value;
        Node *left = NULL;
        Node *right = NULL;
        int N = 1;
        int height = 1;

        Node(Key key, Value value){
            this->key=key;
            this->value=value;
        }

        Node(const Node* node){
            this->key = key;
            this->value = value;
            this->height = height;
            this->left=node->left;
            this->right=node->right;
            this->N = node->N;
        }
    };
    void destory(Node *node){
        if(node==NULL)
            return;
        destory(node->left);
        destory(node->right);
        delete node;
    }

    Node * root;

    /**
     * 通过node的子节点计算node的高度，旋转之后使用
     * @param node
     * @return
     */
    int height(Node* node){
        if(node==NULL) return 0;
        Node* left = node->left;
        Node* right = node->right;

        return max(left==NULL?0:left->height,right==NULL?0:right->height)+1;
    }

    Node* rotateLeft(Node * h){
        Node* x = h->right;
        h->right = x->left;
        x->left = h;

        x->N = h->N;
        h->N = 1+size(h->left)+size(h->right);

        h->height=height(h);
        x->height=height(x);

        return x;
    }

    Node* rotateRight(Node* h){
        Node* x = h->left;
        h->left = x->right;
        x->right = h;

        x->N = h->N;
        h->N = 1+size(h->left)+size(h->right);

        h->height=height(h);
        x->height=height(x);

        return x;
    }

    /**
     *                       L
     *                     /   \
     *                   X       R
     *                         /  \
     *                        x    x
     *                       /
     *                      x
     *
     * 以h为根的树，右子树先右旋转，然后h左旋
     * @param h
     * @return
     */
    Node* rotateRightLeft(Node *h){
        h->right = rotateRight(h->right);
        return rotateLeft(h);
    }

    /**
     *                       L
     *                     /   \
     *                     R      X
     *                  /  \
     *                 X    X
     *                     /
     *                    X
     *
     * 以h为根的树，左子树先左旋转，然后h右旋
     * @param h
     * @return
     */
    Node* rotateLeftRight(Node* h){
        h->left=rotateLeft(h->left);
        return rotateRight(h);
    }


    int size(Node* node){
        if(node==NULL) return 0;
        return node->N;
    }

    /**
     * 获取以node为根的平衡因子，定义为左子树的高度减去右子树高度
     * @param node
     * @return
     */
    int getBF(Node* node){
        if(node==NULL) return 0;
        return height(node->left)-height(node->right);
    }

    Node* _balance(Node* node) {
        if (node != NULL) {
            node->N = 1 + size(node->left) + size(node->right);
            node->height = height(node);
        }
        int bf = getBF(node);
        if(bf == -2){
            int rbf = getBF(node->right);
            if(rbf==1){// key插入 node 的 右子树的左子树 RL
                node = rotateRightLeft(node);
            }else if(rbf==-1 || rbf==0){// key插入 node 的 右子树的右子树 RR
                node = rotateLeft(node);
            }
        }else if(bf == 2){
            int lbf = getBF(node->left);
            if(lbf == -1){ // key插入 node 的 左子树的右子树 LR
                node = rotateLeftRight(node);
            }else if(lbf == 1 || lbf==0){//key插入 node 的 左子树的左子树 LL
                node = rotateRight(node);
            }
        }
        node->N = 1 + size(node->left) + size(node->right);
        node->height = height(node);
        return node;
    }

    Node* put(Node* node, Key key, Value value){
        if(node == NULL){
            return new Node(key,value);
        }
        if(node->key==key){
            node->value=value;
        }else if(node->key>key){
            node->left = put(node->left,key,value);
//            if(getBF(node) == 2){//打破平衡
//                if(key>node->left->key){ // key插入 node 的 左子树的右子树 LR
//                    node = rotateLeftRight(node);
//                }else if(key<node->left->key){//key插入 node 的 左子树的左子树 LL
//                    node = rotateRight(node);
//                }
//            }
        }else{
            node->right = put(node->right,key,value);
//            if(getBF(node)==-2){
//                if(key<node->right->key){// key插入 node 的 右子树的左子树 RL
//                    node = rotateRightLeft(node);
//                }else if(key>node->right->key){// key插入 node 的 右子树的右子树 RR
//                    node = rotateLeft(node);
//                }
//            }
        }
        node = _balance(node);
        return node;
    }

    Node * _removeMin(Node* node){
        if(node->left==NULL) {
            Node* right = node->right;
            delete node;
            return right;
        }
        node->left = _removeMin(node->left);
        node = _balance(node);
        return node;
    }

    Node * _removeMax(Node* node){
        if(node->right==NULL) {
            Node* left = node->left;
            delete node;
            return left;
        }
        node->left = _removeMax(node->right);
        node = _balance(node);
        return node;
    }

    Node* _remove(Node* node, Key key){
        if(node == NULL)
            return NULL;
        if(node->key>key){
            node->left=_remove(node->left,key);
        }else if(node->key<key){
            node->right=_remove(node->right,key);
        }else{
            if(node->right==NULL && node->left==NULL){
                delete node;
                return NULL;
            }else if(node->right!=NULL){
                Node* succeed = _minNum(node->right);//取node后继,需要拷贝一份
                node->key = succeed->key;
                node->value = succeed->value;
                node->right = _removeMin(node->right);
            }else if(node->left!=NULL){
                Node* pre = _maxNum(node->left);//取node前驱,需要拷贝一份
                node->key = pre->key;
                node->value = pre->value;
                node->left = _removeMax(node->left);
            }
        }
        node = _balance(node);
        return node;
    }

    Node*  _maxNum(Node* node){
        while(node->right){
            node = node->right;
        }
        return node;
    }

    Node* _minNum(Node* node){
        while(node->left){
            node = node->left;
        }
        return node;
    }
    bool _contain(Node * node, Key key){
        if(node == NULL)
            return false;
        if(node->key==key){
            return true;
        }
        if(node->key>key){
            return _contain(node->left,key);
        }
        if(node->key<key){
            return _contain(node->right,key);
        }
    }

    bool _isBalanced(Node* node){
        if(node==NULL)
            return true;
        if(abs(height(node->left) - height(node->right)) > 1){
            return false;
        }
        return _isBalanced(node->left) && _isBalanced(node->right);
    }

    bool _isBST(Node* node, Key low, Key high){
        if(node == NULL) return true;
        if(low!=NULL && node->key<=low) return false;
        if(high!=NULL && node->key>=high) return false;
        return _isBST(node->left,low,node->key) && _isBST(node->right,node->key,high);
    }

    bool _isSizeConsistent(Node* node){
        if(node == NULL) return true;
        if(node->N!=1+size(node->left)+size(node->right)) return false;
        return _isSizeConsistent(node->right) && _isSizeConsistent(node->left);
    }

    bool _isHeightConsistent(Node* node){
        if(node == NULL) return true;
        if(node->height!=1+max(height(node->left),height(node->right)))
            return false;
        return _isHeightConsistent(node->right) && _isHeightConsistent(node->left);
    }

    int _rank(Node* node, Key key){
        int rank = 0;
        while(node != NULL){
            int leftCount = node->left==NULL?0:node->left->N;
            if(node->key==key){
                return rank+leftCount;
            }else if(node->key<key){
                rank+=leftCount+1;
                node=node->right;
            }else{
                node=node->left;
            }
        }
        return rank;
    }

    /**
     *
     * @param node 当前节点
     * @param preRank 以node为根节点的树中最小节点的排名
     * @param select
     * @return
     */
    Node* _select(Node* node,int preRank,int select){
        int curentRank = (node->left==NULL?0:node->left->N)+preRank;
        if(select==curentRank){
            return node;
        }else if(select>curentRank){
            return _select(node->right,curentRank+1,select);
        }else{
            return _select(node->left,preRank,select);
        }
    }


public:
    AVLTree(){
        root = NULL;
    }
    ~AVLTree(){
        destory(root);
    }
    int size(){
        return size(root);
    }

    void put(Key key,Value value){
        root = put(root,key,value);
    }

    void removeMin(){
        assert(root!=NULL);
        root = _removeMin(root);
    }

    void removeMax(){
        assert(root!=NULL);
        root = _removeMax(root);
    }


    void remove(Key key){
        if(root==NULL){
            return ;
        }
        if(!_contain(root,key)){
            return;
        }
        root = _remove(root,key);
    }

    bool isEmpty(){
        return root==NULL;
    }

    Key* select(int select){
        assert(select>=0 && select<root->N);
        Node* node = _select(root,0,select);
        return &(node->key);
    }

    //小于key的键数量
    int rank(Key key){
        return _rank(root,key);
    }

    bool check(){
        bool ispassed = true;
        if(!isBalanced()) {
            ispassed = false;
            cout << " isBalanced = false" << endl;
        }
        if(!isBST()){
            ispassed = false;
            cout<<" isBST = false"<<endl;
        }
        if(!isSizeConsistent()) {
            ispassed = false;
            cout << " isSizeConsistent = false" << endl;
        }
        if(!isHeightConsistent()) {
            ispassed = false;
            cout << " isHeightConsistent = false" << endl;
        }
        if(!isRankConsistent()) {
            ispassed = false;
            cout << " isRankConsistent = false" << endl;
        }
        return ispassed;
    }

    bool isBalanced(){
        return _isBalanced(root);
    }

    bool isBST(){
        return _isBST(root,NULL,NULL);
    }

    bool isSizeConsistent(){
        return _isSizeConsistent(root);
    }

    bool isHeightConsistent(){
        return _isHeightConsistent(root);
    }

    bool isRankConsistent() {
        for (int i = 0; i < size(); i++)
            if (i != rank(*select(i))) return false;
        return true;
    }

};

//int main() {
//    AVLTree<char,char> avlTree;
//    char s[] = {'S','E','A','R','C','H','X','M','P','L'};
//    for(int i = 0 ; i< 10;i++){
//        avlTree.put(s[i],s[i]);
////        avlTree.check();
//    }
//
////    while(!avlTree.isEmpty()) {
////        avlTree.removeMin();
////        avlTree.check();
////    }
//
////    while(!avlTree.isEmpty()) {
////        avlTree.removeMax();
////        avlTree.check();
////    }
//
//    for(int i = 0 ; i< 10;i++){
//        avlTree.remove(s[i]);
//        avlTree.check();
//    }
//}


#endif //INC_010_ALGORITHM_AVL_H
